package com.data_structure_test.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * avl平衡树
 * 1.提供3种新的遍历方式和实现方式（共6种，查询一定为先序遍历） done
 * 2.删除提供两种版本，标准删除(删除有个选择问题，选择左子树顶替还是右子树顶替)和懒惰删除 ,懒惰删除的好处是，节省了删除操作的时间，（不使用balance）节省logN的操作时间，但是会增加查询时间log(N/2)
 * 3.增加和删除后的平衡，利用循环和递归进行。done
 * 4.提供测试用例测试各种方式的效率。done
 * @param <T>
 */
public class BinaryAvlTree<T> {

    private AvlNode<T> rootNode;

    private int size;

    private class AvlNode<T>{
        AvlNode<T> parent; //循环中序，后序遍历
        T value;
        AvlNode<T> left;
        AvlNode<T> right;
        int height;

        AvlNode(AvlNode<T> parent,T value,AvlNode<T> left,AvlNode<T> right,int height){
            this.parent = parent;
            this.value = value;
            this.left = left;
            this.right = right;
            this.height = height;
        }

        AvlNode(AvlNode<T> parent,T value,AvlNode<T> left,AvlNode<T> right){
            this(parent,value,left,right,0);
        }

    }

    public int size(){
        return size;
    }

    /*查询循环方式
     */
    public boolean containsWhile(T value){
        AvlNode<T> currNode = rootNode;
        int valueHash = value.hashCode(),currHash;
        while(currNode != null){
            currHash = currNode.value.hashCode();
            if(valueHash > currHash){
                currNode = currNode.right;
                continue;
            }else if(valueHash < currHash){
                currNode = currNode.left;
                continue;
            }
            return true;
        }
        return false;
    }

    /**
     * 查询递归方式
     * @param value
     * @return
     */
    public boolean containsRecursion(T value){

        return containsRecursionInner(rootNode,value);
    }

    private boolean containsRecursionInner(AvlNode<T> currNode, T value){
        if(currNode == null) {
            return false;
        }
        if(value.hashCode() > currNode.value.hashCode()){
            return containsRecursionInner(currNode.right,value);
        }else if(value.hashCode() < currNode.value.hashCode()){
            return containsRecursionInner(currNode.left,value);
        }
        return true;
    }

    public List<T> foreachXianRecursive(){
        List<T> list = new ArrayList<>();
        foreachXianRecursiveInner(rootNode,list);
        return list;
    }

    private void foreachXianRecursiveInner(AvlNode<T> node,List<T> list){

        if(node == null){
            return;
        }
        list.add(node.value);
        foreachXianRecursiveInner(node.left,list);
        foreachXianRecursiveInner(node.right,list);

    }

    /**
     * 中序遍历，递归
     * @return
     */
    public List<T> foreachZhongRecursive(){
        List<T> list = new ArrayList<>();
        foreachZhongRecursiveInner(rootNode,list);
        return list;
    }

    private void foreachZhongRecursiveInner(AvlNode<T> node,List<T> list){
        if(node == null){
            return;
        }
        foreachZhongRecursiveInner(node.left,list);
        list.add(node.value);
        foreachZhongRecursiveInner(node.right,list);
    }

    /**
     * 中序遍历，循环
     * @return
     */
    public List<T> foreachZhongWhile(){
        List<T> list = new ArrayList<>();

        AvlNode<T> currNode = rootNode;
        AvlNode<T> tmpNode = null;

        while(currNode != null || tmpNode != null){

            if(currNode == null){
                if(tmpNode.parent == null) {
                    break;
                }
                if(tmpNode == tmpNode.parent.right){
                    list.add(tmpNode.value);
                    if(tmpNode.parent.parent == null){
                        break;
                    }
                    tmpNode = tmpNode.parent.parent;
                }else if(tmpNode == tmpNode.parent.left){
                    tmpNode = tmpNode.parent;
                }
            }

            while (currNode != null){
                tmpNode = currNode;
                list.add(currNode.value);
                currNode = currNode.left;
            }
            if(tmpNode != null){
                currNode = tmpNode.right;
            }

        }

        return list;
    }



    public void insert(T value){
        if(rootNode == null){
            rootNode = new AvlNode<>(null,value,null,null);
        }else {
            insert(null, rootNode, value);
        }
    }

    private AvlNode<T> insert(AvlNode<T> parent,AvlNode<T> root,T value){

        if(root == null){
            root = new AvlNode<>(parent,value,null,null);

        }

        if(value.hashCode() < root.value.hashCode() ){
           root.left = insert(root,root.left,value);
        }else if(value.hashCode() > root.value.hashCode()){
            root.right =insert(root,root.right,value);
        }else{

        }

        balance(root);
        return root;

    }

    /**
     * 平衡
     * @param balanceRoot
     * @return
     */
    private void balance(AvlNode<T> balanceRoot){
        if(calculateHeight(balanceRoot.left) - calculateHeight(balanceRoot.right) > 1){
            if(calculateHeight(balanceRoot.left.left) >= calculateHeight(balanceRoot.left.right)){
                //右旋
                turnRightWithLeftChild(balanceRoot,balanceRoot.left);
            }else{
                turnLeftWithRightChild(balanceRoot.left,balanceRoot.left.right);
                turnRightWithLeftChild(balanceRoot,balanceRoot.left);
            }
        }else if(calculateHeight(balanceRoot.right) - calculateHeight(balanceRoot.left) > 1){
            if(calculateHeight(balanceRoot.right.right) >= calculateHeight(balanceRoot.right.left)){
                //左旋
                turnLeftWithRightChild(balanceRoot,balanceRoot.right);
            }else{
                turnRightWithLeftChild(balanceRoot.right,balanceRoot.right.left);
                turnLeftWithRightChild(balanceRoot,balanceRoot.right);
            }
        }
        balanceRoot.height = max(calculateHeight(balanceRoot.left),calculateHeight(balanceRoot.right)) + 1;
    }

    private void turnRightWithLeftChild(AvlNode<T> fundamentalNode,AvlNode<T> newFundamentalNode){
        if(fundamentalNode != null && newFundamentalNode != null) {
            //因为有parent，选择改值而不是改引用的方式实现
            T tmp = fundamentalNode.value;
            fundamentalNode.value = newFundamentalNode.value;
            fundamentalNode.left = newFundamentalNode.left;
            fundamentalNode.right = newFundamentalNode;
            newFundamentalNode.value = tmp;
            newFundamentalNode.left = newFundamentalNode.right;
            newFundamentalNode.right = null;

            newFundamentalNode.height = max(calculateHeight(newFundamentalNode.left) , calculateHeight(newFundamentalNode.right)) + 1;
            fundamentalNode.height = max(calculateHeight(newFundamentalNode) , calculateHeight(fundamentalNode.left)) + 1;
        }
    }

    private void turnLeftWithRightChild(AvlNode<T> fundamentalNode,AvlNode<T> newFundamentalNode){
        if(fundamentalNode != null && newFundamentalNode != null) {
            //因为有parent，选择改值而不是改引用的方式实现
            T tmp = fundamentalNode.value;
            fundamentalNode.value = newFundamentalNode.value;
            fundamentalNode.right = newFundamentalNode.right;
            fundamentalNode.left = newFundamentalNode;
            newFundamentalNode.value = tmp;
            newFundamentalNode.right = newFundamentalNode.left;
            newFundamentalNode.left = null;

            newFundamentalNode.height = max(calculateHeight(newFundamentalNode.left) , calculateHeight(newFundamentalNode.right)) + 1;
            fundamentalNode.height = max(calculateHeight(newFundamentalNode) , calculateHeight(fundamentalNode.right)) + 1;
        }
    }


    private int calculateHeight(AvlNode<T> node){
        return node == null ? -1 : node.height;
    }


    public int max(int first, int second){
        return first > second ? first : second;
    }


    public void lazyRemove(){

    }



    public static void main(String[] args){


    }

}
